package com.ddshuai.easy;

import java.util.Stack;

/**
 * @author ddshuai
 * @version 1.0.0
 * @date 2018/3/29
 * @modify desc
 * @2018/3/29 新增        1.0.0
 * <p>
 * 数数并说序列是一个整数序列，第二项起每一项的值为对前一项的计数，其前五项如下：
 * 1.     1
 * 2.     11
 * 3.     21
 * 4.     1211
 * 5.     111221
 * <p>
 * 1 被读作 "一个一" 即 11。
 * 11 被读作  "两个一" 即 21。
 * 21 被读作  "一个二 和 一个一" 即 1211。
 * <p>
 * 给一个正整数 n ，输出数数并说序列的第 n 项。
 * <p>
 * 注意：该整数序列的每项都输出为字符串。
 * <p>
 * 输入: 1
 * 输出: "1"
 * <p>
 * 输入: 4
 * 输出: "1211"
 */
public class CountAndSay {
    public static String countAndSay(int n) {

        String init = "1";
        for (int i = 0; i < n - 1; i++) {
            Stack<Character> stack = new Stack<>();
            StringBuilder tmp = new StringBuilder("");
            int count = 0;
            Character pre = null;

            char[] chars = new StringBuilder(init).reverse().toString().toCharArray();
            for (char aChar : chars) {
                stack.push(aChar);
            }

            while (!stack.isEmpty()) {
                if (pre == null) {
                    pre = stack.pop();
                    count++;

                    if (stack.isEmpty()) {
                        //结算
                        tmp.append(String.valueOf(count)).append(String.valueOf(pre));
                    }
                } else {
                    Character curr = stack.pop();
                    if (curr.equals(pre)) {
                        count++;
                        if (stack.isEmpty()) {
                            //结算
                            tmp.append(String.valueOf(count)).append(String.valueOf(pre));
                        }
                    } else {
                        //结算
                        tmp.append(String.valueOf(count)).append(String.valueOf(pre));
                        //重置计数
                        count = 1;
                        pre = curr;

                        if (stack.isEmpty()) {
                            //结算
                            tmp.append(String.valueOf(1)).append(String.valueOf(curr));
                        }
                    }
                }

            }

            init = tmp.toString();
        }

        return init;
    }

    /**
     * 比我的高效
     *
     * @param n
     * @return
     */
    public String countAndSay2(int n) {
        StringBuilder curr = new StringBuilder("1");
        StringBuilder prev;
        int count;
        char say;
        for (int i = 1; i < n; i++) {
            prev = curr;
            curr = new StringBuilder();
            count = 1;
            say = prev.charAt(0);

            for (int j = 1, len = prev.length(); j < len; j++) {
                if (prev.charAt(j) != say) {
                    curr.append(count).append(say);
                    count = 1;
                    say = prev.charAt(j);
                } else count++;
            }
            curr.append(count).append(say);
        }
        return curr.toString();
    }

    public static void main(String[] args) {
        System.out.println(countAndSay(2));
    }
}
